package arithmetic1.greed;

import java.util.HashMap;
import java.util.HashSet;

/*
    贪心算法解决集合覆盖问题
 */
public class GreedArithmetic {
    public static void main(String[] args) {
        //存储所有电台的名字和覆盖范围
        HashMap<String, HashSet<String>> broadcasts=new HashMap<>();
        HashSet<String> k1=new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");

        HashSet<String> k2=new HashSet<>();
        k2.add("广州");
        k2.add("上海");
        k2.add("深圳");

        HashSet<String> k3=new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");

        HashSet<String> k4=new HashSet<>();
        k4.add("上海");
        k4.add("天津");

        HashSet<String> k5=new HashSet<>();
        k5.add("杭州");
        k5.add("大连");

        broadcasts.put("k1",k1);
        broadcasts.put("k2",k2);
        broadcasts.put("k3",k3);
        broadcasts.put("k4",k4);
        broadcasts.put("k5",k5);

        //所有要覆盖的地区
        HashSet<String> allAreas=new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");

        //记录选择的所有电台名字
        HashSet<String> selects=new HashSet<>();
        //记录每次最优的电台名字
        String maxKey;
        //一个临时集合来存储每次选择的电台信息
        HashSet<String> temp=new HashSet<>();
        //遍历所有电台
        while (allAreas.size()>0){  //当还有地区未覆盖时一直寻找电台来覆盖未覆盖地区
            maxKey=null;    //将每次保存的maxKey清空
            //遍历所有电台,从其中选取目前能覆盖最多未覆盖地区的电台加入到selects中
            for(String key:broadcasts.keySet()){
                if(!selects.contains(key)){  //如果这个电台没有被选中
                    temp.clear();   //
                    HashSet<String> area=broadcasts.get(key);
                    temp.addAll(area);
                    //保留没有覆盖的地区
                    temp.retainAll(allAreas);
                    //当maxKey为null，或者这次的选择优于之前的maxKey这个选择
                    if(maxKey!=null){
                        broadcasts.get(maxKey).retainAll(allAreas);
                    }
                    if(temp.size()>0 && (maxKey==null || temp.size()>broadcasts.get(maxKey).size())){
                        //将maxKey更新
                        maxKey=key;
                    }
                }
            }
            //得到了每次的最优选择后
            if(maxKey!=null){
                //将最优选择加入到selects中
                selects.add(maxKey);
                //将这次选择的新区域从未覆盖地区删除
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("结果为:"+ selects);
    }

}
